In modern digital data transmission (wireless telephony, wireless data transmission, optical disk transmission to a player, music players receiving music data, and so on), a source encoder can compress the data to be transmitted for efficiency and then a channel encoder can receive the compressed data and add redundancy to it to protect the data against noise in the transmission channel. The receiver (sometimes referred to as the “sink”) at the other end of the channel receives the encoded data and uses a channel decoder to perform the inverse of channel encoding, followed by a source decoder which performs the inverse of source encoding. The decoded information is then played by the sink, e.g., by an optical disk player or music player or receiving telephone as audio, or is otherwise used and/or stored by the receiver.
Present principles focus on channel encoding. Channel encoding typically works by sending a piece of data sought to be communicated, referred to as a “data word”, through a transformation to produce a “code word” that is better protected against errors than the data word from which it is derived and thus is more suitable for transmission than the data word. For present purposes suffice it to say that linear block encoders, which multiply a data word using a matrix, have been used for this purpose because they are able to achieve an acceptable tradeoff of offering significant (albeit not absolute) protection against noise, commonly expressed in terms of the error rates such as bit error rates (BER) that result from noise, while being of sufficiently “low complexity” in terms of the amount of computation they require. Higher complexity encoding schemes that reduce the BER of a received signal but require too much computation for expected data transmission rates are of little practical use.
A newer type of linear block code is the polar code, which improves on older codes by being able to achieve channel capacity, i.e., by being able to encode data such that the full capacity of the transmission channel can be exploited. Channel polarization refers to the fact that given a binary-input discrete memoryless channel W with symmetric capacity I(W), it is possible to synthesize, out of N independent copies of W, a second set of N binary-input channels WN(i), 1≦i≦N such that as N becomes large, a fraction I(W) of the synthesized channels become near perfect while the remaining fraction of channels become near useless. Codes constructed on the basis of this idea are called polar codes. Non-systematic polar encoders effect polar coding by collecting an input data word d and a fixed word b into a transform input word u and by multiplying it with a transform matrix G to render a code word x, i.e., x=uG.
The transform matrix G used in polar codes is based on Kronecker products, and its dimension is established as appropriate for the desired channel rate or capacity. Polar coding essentially amounts to selecting some of the elements of the transform input word u to carry the data word d while “freezing” (not using for encoding) the remainder of the elements of the transform input word. The elements of the transform input word that are selected to carry the data word d are those that in effect “see” the relatively good channels created by channel polarization, while the elements of b that are frozen “see” the relatively bad channels. In my paper which introduced polar codes, entitled “Channel Polarization: A Method for Constructing Capacity-Achieving Code for Symmetric Binary-Input Memoryless Channels”, IEEE Trans. Inf. Theory, volume 55, pages 3051-3073 (July 2009), incorporated herein by reference and included in the file history of this application, I describe how to carry out channel polarization and transmit data using the “good” channels.
The problem sought to be addressed by present principles is as follows. The polar codes described in the above-referenced paper are non-systematic polar codes, meaning that the information bits do not appear as part of the code word transparently. Systematic codes in general, in which information bits appear as part of the code word transparently, can provide better error reduction performance than their non-systematic counterparts.
As recognized herein, however, conventional techniques cannot be used to transform a non-systematic polar code into a systematic polar code because doing so destroys the requisite recursive structure of the Kronecker power-based transform matrix G typically used in polar codes, which in turn implicates an unacceptably high encoder complexity. Present principles critically recognize that a systematic encoder for polar codes desired to maximize channel capacity exploitation, maximize immunity from noise, while exhibiting a low computation complexity to enable it to feasibly operate in expected data transmission environments.